import java.util.Random;

public class QuickSort2 {
    public static void main(String[] args) {
//        快速排序：
//        第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
//        比基准数小的全部在左边，比基准数大的全部在右边。
//        后面以此类推
//        int[] arr={6,1,2,7,9,3,4,5,10,8};
//        quickSort(arr,0,arr.length - 1);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
        Random r = new Random();
        int[] arr = new int[10];//创建随机数组来测试
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(100 + 1);//创建10个随机数,把随机数放进数组里
        }
        //打印排序前的数组
        System.out.print("排序前的数组:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        quickSort(arr,0,arr.length - 1);//对数组进行快速排序

        System.out.print("排序后的数组:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    //参数一:我们要排序的数组
    //参数二:要排序的数组的起始索引
    //参数三,要排序数组的结束索引
    public static void quickSort(int[] arr,int i,int j){
        if(i >= j){
            return;//递归结束
        }
        int start = i;//记录数组的起始位置
        int end = j;
        int baseNumber = arr[i];
        while(start != end){
            //用end ,从后开始往前找比基准数小的数字
            while(true){
                if(end <= start || arr[end] < baseNumber){
                    break;
                }
                end--;
            }
            //用start,从前开始往后找比基准数大的数字
            while(true){
                if(end <= start || arr[start] > baseNumber){//找到值后结束循环,并挪动start指向的位置
                    break;
                }
                start++;
            }
            //把end和start元素进行交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //基准数归位,将start下标的和基准数交换位置
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
//        int temp = arr[start];
//        arr[start] = baseNumber;
//        baseNumber = temp;
        //虽然arr[i]=baseNumber 此处改变的事baseNumber的值,并没有改变数组中的基准值,所以要用arr[i]来实现交换
        quickSort(arr,i,start - 1);
        quickSort(arr,start + 1 ,j);
    }
}
